package sword_to_1;

import node.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LeeCode_32_1 {
    public static void main(String[] args) {

    }
    private static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        int d = getDepth(root, 0);
        for (int i = 0; i < d; i++) {
            list.add(new ArrayList<>());
        }
        dfs(root, list, 0);
        for (int i = 0; i < list.size(); i++) {
            if (i % 2 == 1){
                List<Integer> son = list.get(i);
                Collections.reverse(son);
            }
        }
        return list;
    }
    private static int getDepth(TreeNode node, int depth){
        if (node == null)
            return depth;
        return Math.max(getDepth(node.left, depth + 1), getDepth(node.right, depth + 1));
    }
    private static void dfs(TreeNode node, List<List<Integer>> list, int depth){
        if (node == null)
            return;
        list.get(depth).add(node.val);
        dfs(node.left, list, depth + 1);
        dfs(node.right, list, depth + 1);
    }
}
